Algoritmos genéticos e processamento paralelo aplicados à definição e treinamento de redes neurais perceptron de múltiplas camadas

ln this work, it was deveIoped a parallel cooperative genetic algorithm with different evolution behaviors to train and to define architectures for MuItiIayer Perceptron neural networks. MuItiIayer Perceptron neural networks are very powerful tools and had their use extended vastIy due to their abiIity of providing great resuIts to a broad range of appIications. The combination of genetic algorithms and parallel processing can be very powerful when applied to the Iearning process of the neural network, as well as to the definition of its architecture since this procedure can be very slow, usually requiring a lot of computational time. AIso, research work combining and appIying evolutionary computation into the design of neural networks is very useful since most of the Iearning algorithms deveIoped to train neural networks only adjust their synaptic weights, not considering the design of the networks architecture. Furthermore, the use of cooperation in the genetic algorithm allows the interaction of different populations, avoiding local minima and helping in the search of a promising solution, acceIerating the evolutionary process. Finally, individuaIs and evolution behavior can be exclusive on each copy of the genetic algorithm running in each task enhancing the diversity of populations

Entropia conjunta de espaço e reqüência espacial estimada através da discriminação de estímulos espaciais com luminância e cromaticidade moduladas por funções de Gábor: implicações para o processamento paralelo de informação no sistema visual humano

O objetivo deste estudo foi estimar a entropia conjunta do sistema visual humano no domínio do espaço e no domínio das freqüências espaciais através de funções psicométricas. Estas foram obtidas com testes de discriminação de estímulos com luminância ou cromaticidade moduladas por funções de Gábor. A essência do método consistiu em avaliar a entropia no domínio do espaço, testando-se a capacidade do sujeito em discriminar estímulos que diferiam apenas em extensão espacial, e avaliar a entropia no domínio das freqüências espaciais, testando-se a capacidade do sujeito em discriminar estímulos que diferiam apenas em freqüência espacial. A entropia conjunta foi calculada, então, a partir desses dois valores individuais de entropia. Três condições visuais foram estudadas: acromática, cromática sem correção fina para eqüiluminância e cromática com correção para eqüiluminância através de fotometria com flicker heterocromático. Quatro sujeitos foram testados nas três condições, dois sujeitos adicionais foram testados na condição cromática sem eqüiluminância fina e um sétimo sujeito também fez o teste acromático. Todos os sujeitos foram examinados por oftalmologista e considerados normais do ponto de vista oftálmico, não apresentando relato, sintomas ou sinais de disfunções visuais ou de moléstias potencialmente capazes de afetar o sistema visual. Eles tinham acuidade visual normal ou corrigida de no mínimo 20/30. O trabalho foi aprovado pela Comissão de Ética em Pesquisa do Núcleo de Medicina Tropical da UFPA e obedeceu às recomendações da Declaração de Helsinki. As funções de Gábor usadas para modulação de luminância ou cromaticidade compreenderam redes senoidais unidimensionais horizontais, moduladas na direção vertical, dentro de envelopes gaussianos bidimensionais cuja extensão espacial era medida pelo desvio padrão da gaussiana. Os estímulos foram gerados usando-se uma rotina escrita em Pascal num ambiente Delphi 7 Enterprise. Foi utilizado um microcomputador Dell Precision 390 Workstation e um gerador de estímulos CRS VSG ViSaGe para exibir os estímulos num CRT de 20”, 800 x 600 pixels, 120 Hz, padrão RGB, Mitsubishi Diamond Pro 2070SB. Nos experimentos acromáticos, os estímulos foram gerados pela modulação de luminância de uma cor branca correspondente à cromaticidade CIE1931 (x = 0,270; y = 0,280) ou CIE1976 (u’ = 0,186; v’= 0,433) e tinha luminância média de 44,5 cd/m2. Nos experimentos cromáticos, a luminância média foi mantida em 15 cd/m2 e foram usadas duas series de estímulos verde-vermelhos. Os estímulos de uma série foram formados por duas cromaticidades definidas no eixo M-L do Espaço de Cores DKL (CIE1976: verde, u’=0,131, v’=0,380; vermelho, u’=0,216, v’=0,371). Os estímulos da outra série foram formados por duas cromaticidades definidas ao longo de um eixo horizontal verde-vermelho definido no Espaço de Cores CIE1976 (verde, u’=0,150, v’=0,480; vermelho, u’=0,255, v’=0,480). Os estímulos de referência eram compostos por redes de três freqüências espaciais diferentes (0,4, 2 e 10 ciclos por grau) e envelope gaussiano com desvio padrão de 1 grau. Os estímulos de testes eram compostos por uma entre 19 freqüências espaciais diferentes em torno da freqüência espacial de referência e um entre 21 envelopes gaussianos diferentes com desvio padrão em torno de 1 grau. Na condição acromática, foram estudados quatro níveis de contraste de Michelson: 2%, 5%, 10% e 100%. Nas duas condições cromáticas foi usado o nível mais alto de contraste agregado de cones permitidos pelo gamut do monitor, 17%. O experimento consistiu numa escolha forçada de dois intervalos, cujo procedimento de testagem compreendeu a seguinte seqüência: i) apresentação de um estímulo de referência por 1 s; ii) substituição do estímulo de referência por um fundo eqüiluminante de mesma cromaticidade por 1 s; iii) apresentação do estímulo de teste também por 1 s, diferindo em relação ao estímulo de referência seja em freqüência espacial, seja em extensão espacial, com um estímulo sonoro sinalizando ao sujeito que era necessário responder se o estímulo de teste era igual ou diferente do estímulo de referência; iv) substituição do estímulo de teste pelo fundo. A extensão espacial ou a freqüência espacial do estímulo de teste foi mudada aleatoriamente de tentativa para tentativa usando o método dos estímulos constantes. Numa série de 300 tentativas, a freqüencia espacial foi variada, noutra série também de 300 tentativas, a extensão espacial foi variada, sendo que cada estímulo de teste em cada série foi apresentado pelo menos 10 vezes. A resposta do indivíduo em cada tentativa era guardada como correta ou errada para posterior construção das curvas psicométricas. Os pontos experimentais das funções psicométricas para espaço e freqüência espacial em cada nível de contraste, correspondentes aos percentuais de acertos, foram ajustados com funções gaussianas usando-se o método dos mínimos quadrados. Para cada nível de contraste, as entropias para espaço e freqüência espacial foram estimadas pelos desvios padrões dessas funções gaussianas e a entropia conjunta foi obtida multiplicando-se a raiz quadrada da entropia para espaço pela entropia para freqüência espacial. Os valores de entropia conjunta foram comparados com o mínimo teórico para sistemas lineares, 1/4π ou 0,0796. Para freqüências espaciais baixas e intermediárias, a entropia conjunta atingiu níveis abaixo do mínimo teórico em contrastes altos, sugerindo interações não lineares entre dois ou mais mecanismos visuais. Este fenômeno occorreu em todas as condições (acromática, cromática e cromática eqüiluminante) e foi mais acentuado para a frequência espacial de 0,4 ciclos / grau. Uma possível explicação para este fenômeno é a interação não linear entre as vias visuais retino-genículo-estriadas, tais como as vias K, M e P, na área visual primária ou em níveis mais altos de processamento neural.

Paralelização do algoritmo FDK para reconstrução 3D de imagens tomográficas usando unidades gráficas de processamento e CUDA-C

A obtenção de imagens usando tomografia computadorizada revolucionou o diagnóstico de doenças na medicina e é usada amplamente em diferentes áreas da pesquisa científica. Como parte do processo de obtenção das imagens tomográficas tridimensionais um conjunto de radiografias são processadas por um algoritmo computacional, o mais usado atualmente é o algoritmo de Feldkamp, David e Kress (FDK). Os usos do processamento paralelo para acelerar os cálculos em algoritmos computacionais usando as diferentes tecnologias disponíveis no mercado têm mostrado sua utilidade para diminuir os tempos de processamento. No presente trabalho é apresentada a paralelização do algoritmo de reconstrução de imagens tridimensionais FDK usando unidades gráficas de processamento (GPU) e a linguagem CUDA-C. São apresentadas as GPUs como uma opção viável para executar computação paralela e abordados os conceitos introdutórios associados à tomografia computadorizada, GPUs, CUDA-C e processamento paralelo. A versão paralela do algoritmo FDK executada na GPU é comparada com uma versão serial do mesmo, mostrando maior velocidade de processamento. Os testes de desempenho foram feitos em duas GPUs de diferentes capacidades: a placa NVIDIA GeForce 9400GT (16 núcleos) e a placa NVIDIA Quadro 2000 (192 núcleos).

Um algoritmo em paralelo para solução de equações diferenciais evolutivas

Este trabalho que envolve matemática aplicada e processamento paralelo: seu objetivo é avaliar uma estratégia de implementação em paralelo para algoritmos de diferenças finitas que aproximam a solução de equações diferenciais de evolução. A alternativa proposta é a substituição dos produtos matriz-vetor efetuados sequencialmente por multiplicações matriz-matriz aceleradas pelo método de Strassen em paralelo. O trabalho desenvolve testes visando verificar o ganho computacional relacionado a essa estratégia de paralelização, pois as aplicacações computacionais, que empregam a estratégia sequencial, possuem como característica o longo período de computação causado pelo grande volume de cálculo. Inclusive como alternativa, nós usamos o algoritmo em paralelo convencional para solução de algoritmos explícitos para solução de equações diferenciais parciais evolutivas no tempo. Portanto, de acordo com os resultados obtidos, nós observamos as características de cada estratégia em paralelo, tendo como principal objetivo diminuir o esforço computacional despendido.

DistributedCL: middleware de processamento distribuído em GPU com interface da API OpenCL.

Este trabalho apresenta a proposta de um middleware, chamado DistributedCL, que torna transparente o processamento paralelo em GPUs distribuídas. Com o suporte do middleware DistributedCL uma aplicação, preparada para utilizar a API OpenCL, pode executar de forma distribuída, utilizando GPUs remotas, de forma transparente e sem necessidade de alteração ou nova compilação do seu código. A arquitetura proposta para o middleware DistributedCL é modular, com camadas bem definidas e um protótipo foi construído de acordo com a arquitetura, onde foram empregados vários pontos de otimização, incluindo o envio de dados em lotes, comunicação assíncrona via rede e chamada assíncrona da API OpenCL. O protótipo do middleware DistributedCL foi avaliado com o uso de benchmarks disponíveis e também foi desenvolvido o benchmark CLBench, para avaliação de acordo com a quantidade dos dados. O desempenho do protótipo se mostrou bom, superior às propostas semelhantes, tendo alguns resultados próximos do ideal, sendo o tamanho dos dados para transmissão através da rede o maior fator limitante.

Política de escalonamento de recursos computacionais em clusters de física de altas energias

Este trabalho apresenta uma proposta para permitir o uso compartilhado dos recursos computacionais utilizados em um cluster de forma a atender simultaneamente aos quatro experimentos do CERN. A abordagem adotada utiliza o conceito de contratos, onde os requisitos e restrições de cada experimento são descritos em perfis, e uma política de alocação de recursos é definida para manter a utilização dos recursos de forma a atender aos perfis. Propomos um modelo de arquitetura para gerenciar o uso compartilhado de um cluster pelas quatro Organizações Virtuais do LHC. Este modelo de arquitetura é composto de elementos comuns a um cluster típico da Tier-2, acrescidos de funcionalidades para controlar a admissão de novos jobs de todas as Organizações Virtuais do LHC. Este modelo monitora a utilização de recursos do cluster por cada OV, aloca recursos para cada job de acordo com uma política estabelecida para o cluster de forma a procurar respeitar os requisitos de cada uma delas. Definimos um algoritmo para o escalonamento de jobs, que utiliza mecanismos de preempção para controlar a alocação de nós do cluster dependendo o uso corrente e acumulado de recursos por cada OV. Este algoritmo é executado em um dos elementos da arquitetura batizado de broker, dado que o mesmo intermedeia a chegada de novos jobs e a alocação dos nós do cluster, e tem com objetivo manter o controle dos contratos de cada OV. A simulação da arquitetura proposta foi feita no simulador de grades GridSim e os resultados obtidos foram avaliados.

Implementação de algoritmos genéticos paralelos em uma arquitetura MPSoC.

Essa dissertação apresenta a implementação de um algoritmo genético paralelo utilizando o modelo de granularidade grossa, também conhecido como modelo das ilhas, para sistemas embutidos multiprocessados. Os sistemas embutidos multiprocessados estão tornando-se cada vez mais complexos, pressionados pela demanda por maior poder computacional requerido pelas aplicações, principalmente de multimídia, Internet e comunicações sem fio, que são executadas nesses sistemas. Algumas das referidas aplicações estão começando a utilizar algoritmos genéticos, que podem ser beneficiados pelas vantagens proporcionadas pelo processamento paralelo disponível em sistemas embutidos multiprocessados. No algoritmo genético paralelo do modelo das ilhas, cada processador do sistema embutido é responsável pela evolução de uma população de forma independente dos demais. A fim de acelerar o processo evolutivo, o operador de migração é executado em intervalos definidos para realizar a migração dos melhores indivíduos entre as ilhas. Diferentes topologias lógicas, tais como anel, vizinhança e broadcast, são analisadas na fase de migração de indivíduos. Resultados experimentais são gerados para a otimização de três funções encontradas na literatura.

Novel hardware and software combination for automotive motorsport vehicles based on direct processing of graphical functions

The main motivation for the work presented here began with previously conducted experiments with a programming concept at the time named "Macro". These experiments led to the conviction that it would be possible to build a system of engine control from scratch, which could eliminate many of the current problems of engine management systems in a direct and intrinsic way. It was also hoped that it would minimize the full range of software and hardware needed to make a final and fully functional system. Initially, this paper proposes to make a comprehensive survey of the state of the art in the specific area of software and corresponding hardware of automotive tools and automotive ECUs. Problems arising from such software will be identified, and it will be clear that practically all of these problems stem directly or indirectly from the fact that we continue to make comprehensive use of extremely long and complex "tool chains". Similarly, in the hardware, it will be argued that the problems stem from the extreme complexity and inter-dependency inside processor architectures. The conclusions are presented through an extensive list of "pitfalls" which will be thoroughly enumerated, identified and characterized. Solutions will also be proposed for the various current issues and for the implementation of these same solutions. All this final work will be part of a "proof-of-concept" system called "ECU2010". The central element of this system is the before mentioned "Macro" concept, which is an graphical block representing one of many operations required in a automotive system having arithmetic, logic, filtering, integration, multiplexing functions among others. The end result of the proposed work is a single tool, fully integrated, enabling the development and management of the entire system in one simple visual interface. Part of the presented result relies on a hardware platform fully adapted to the software, as well as enabling high flexibility and scalability in addition to using exactly the same technology for ECU, data logger and peripherals alike. Current systems rely on a mostly evolutionary path, only allowing online calibration of parameters, but never the online alteration of their own automotive functionality algorithms. By contrast, the system developed and described in this thesis had the advantage of following a "clean-slate" approach, whereby everything could be rethought globally. In the end, out of all the system characteristics, "LIVE-Prototyping" is the most relevant feature, allowing the adjustment of automotive algorithms (eg. Injection, ignition, lambda control, etc.) 100% online, keeping the engine constantly working, without ever having to stop or reboot to make such changes. This consequently eliminates any "turnaround delay" typically present in current automotive systems, thereby enhancing the efficiency and handling of such systems.

Paralelização automática de algoritmos matriciais

Tese de dout., Engenharia Electrónica e Computação, Faculdade de Ciências e Tecnologia, Univ. do Algarve, 2003

Paralelização de métodos de resolução de sistemas lineares esparsos com o DECK em um Cluster de PCs

O objetivo desta dissertação é a paralelização e a avaliação do desempenho de alguns métodos de resolução de sistemas lineares esparsos. O DECK foi utilizado para implementação dos métodos em um cluster de PCs. A presente pesquisa é motivada pela vasta utilização de Sistemas de Equações Lineares em várias áreas científicas, especialmente, na modelagem de fenômenos físicos através de Equações Diferenciais Parciais (EDPs). Nessa área, têm sido desenvolvidas pesquisas pelo GMC-PAD – Grupo de Matemática da Computação e Processamento de Alto Desempenho da UFRGS, para as quais esse trabalho vem contribuindo. Outro fator de motivação para a realização dessa pesquisa é a disponibilidade de um cluster de PCs no Instituto de Informática e do ambiente de programação paralela DECK – Distributed Execution and Communication Kernel. O DECK possibilita a programação em ambientes paralelos com memória distribuída e/ou compartilhada. Ele está sendo desenvolvido pelo grupo de pesquisas GPPD – Grupo de Processamento Paralelo e Distribuído e com a paralelização dos métodos, nesse ambiente, objetiva-se também validar seu funcionamento e avaliar seu potencial e seu desempenho. Os sistemas lineares originados pela discretização de EDPs têm, em geral, como características a esparsidade e a numerosa quantidade de incógnitas. Devido ao porte dos sistemas, para a resolução é necessária grande quantidade de memória e velocidade de processamento, característicos de computações de alto desempenho. Dois métodos de resolução foram estudados e paralelizados, um da classe dos métodos diretos, o Algoritmo de Thomas e outro da classe dos iterativos, o Gradiente Conjugado. A forma de paralelizar um método é completamente diferente do outro. Isso porque o método iterativo é formado por operações básicas de álgebra linear, e o método direto é formado por operações elementares entre linhas e colunas da matriz dos coeficientes do sistema linear. Isso permitiu a investigação e experimentação de formas distintas de paralelismo. Do método do Gradiente Conjugado, foram feitas a versão sem précondicionamento e versões pré-condicionadas com o pré-condicionador Diagonal e com o pré-condicionador Polinomial. Do Algoritmo de Thomas, devido a sua formulação, somente a versão básica foi feita. Após a paralelização dos métodos de resolução, avaliou-se o desempenho dos algoritmos paralelos no cluster, através da realização de medidas do tempo de execução e foram calculados o speedup e a eficiência. As medidas empíricas foram realizadas com variações na ordem dos sistemas resolvidos e no número de nodos utilizados do cluster. Essa avaliação também envolveu a comparação entre as complexidades dos algoritmos seqüenciais e a complexidade dos algoritmos paralelos dos métodos. Esta pesquisa demonstra o desempenho de métodos de resolução de sistemas lineares esparsos em um ambiente de alto desempenho, bem como as potencialidades do DECK. Aplicações que envolvam a resolução desses sistemas podem ser realizadas no cluster, a partir do que já foi desenvolvido, bem como, a investigação de précondicionadores, comparação do desempenho com outros métodos de resolução e paralelização dos métodos com outras ferramentas possibilitando uma melhor avaliação do DECK.

Particionamento de domínio e balanceamento de carga no modelo HIDRA

A paralelização de aplicaçõpes envolvendo a solução de problemas definidos sob o escopo da Dinâmica dos Fluidos Computacional normalmente é obtida via paralelismo de dados, onde o domínio da aplicação é dividido entre os diversos processadores, bem como a manutenção do balancecamento durante a execução é um problema complexo e diversas heurísticas têm sido desenvolvidas. Aplicações onde a simulação é dividida em diversas fases sobre partes diferentes do domínio acrescentam uma dificuldade maior ao particionamento, ao se buscar a distirbuição equlibrada das cargas em todas as fases. este trabalho descreve a implementação de mecanismos de particionamento e balanceamento de carga em problemas multi-fase sobre clusters de PCs. Inicialmente é apresentada a aplicação desenvolvida, um modelo de circulação e transporte de susbtâncias sobre corpos hídricos 2D e 3 D, que pode ser utilizado para modelar qualquer corpo hídrico a partir da descrição de sua geometria, batimetria e condições de contorno. Todo o desenvolvimento e testes do modelo foi feito utilizando como caso de estudo o domínio do Lago Guaíba, em Porto Alegre. Após, são descritas as principais heurísticas de particionamento de domínio de aplicações multi-fase em clusters, bem como mecanismos para balanceamento de carga para este tipo de aplicação. Ao final, é apresentada a solução proposta e desenvolvida, bem como os resultados obtidos com a mesma.

ONNIS-GI: uma rede neural oscilatória para segmentação de imagens implementada em arquitetura maciçamente paralela

A presente tese apresenta a concepção de uma rede neural oscilatória e sua realização em arquitetura maciçamente paralela, a qual é adequada à implementação de chips de visão digitais para segmentação de imagens. A rede proposta, em sua versão final, foi denominada ONNIS-GI (Oscillatory Neural Network for Image Segmentation with Global Inhibition) e foi inspirada em uma rede denominada LEGION (Locally Excitatory Globally Inhibitory Oscillator Network), também de concepção recente. Inicialmente, é apresentada uma introdução aos procedimentos de segmentação de imagens, cujo objetivo é o de situar e enfatizar a importância do tema abordado dentro de um contexto abrangente, o qual inclui aplicações de visão artificial em geral. Outro aspecto abordado diz respeito à utilização de redes neurais artificiais em segmentação de imagens, enfatizando as denominadas redes neurais oscilatórias, as quais têm apresentado resultados estimulantes nesta área. A implementação de chips de visão, integrando sensores de imagens e redes maciçamente paralelas de processadores, é também abordada no texto, ressaltando o objetivo prático da nova rede neural proposta. No estudo da rede LEGION, são apresentados resultados de aplicações originais desenvolvidas em segmentação de imagens, nos quais é verificada sua propriedade de separação temporal dos segmentos. A versão contínua da rede, um arranjo paralelo de neurônios baseados em equações diferenciais, apresenta elevada complexidade computacional para implementação em hardware digital e muitos parâmetros, com procedimento de ajuste pouco prático. Por outro lado, sua arquitetura maciçamente paralela apresenta-se particularmente adequada à implementação de chips de visão analógicos com capacidade de segmentação de imagens. Com base nos bons resultados obtidos nas aplicações desenvolvidas, é proposta uma nova rede neural, em duas versões, ONNIS e ONNIS-GI, as quais suplantam a rede LEGION em diversos aspectos relativos à implementação prática. A estrutura dos elementos de processamento das duas versões da rede, sua implementação em arquitetura maciçamente paralela e resultados de simulações e implementações em FPGA são apresentados, demonstrando a viabilidade da proposta. Como resultado final, conclui-se que a rede ONNIS-GI apresenta maior apelo de ordem prática, sendo uma abordagem inovadora e promissora na solução de problemas de segmentação de imagens, possuindo capacidade para separar temporalmente os segmentos encontrados e facilitando a posterior identificação dos mesmos. Sob o ponto de vista prático, a nova rede pode ser utilizada para implementar chips de visão digitais com arquitetura maciçamente paralela, explorando a velocidade de tais topologias e apresentando também flexibilidade para implementação de procedimentos de segmentação de imagens mais sofisticados.

Métodos multigrid paralelos em malhas não estruturadas aplicados à simulação de problemas de dinâmica de fluidos computacional e transferência de calor

Fenômenos naturais, tecnológicos e industriais podem, em geral, ser modelados de modo acurado através de equações diferenciais parciais, definidas sobre domínios contínuos que necessitam ser discretizados para serem resolvidos. Dependendo do esquema de discretização utilizado, pode-se gerar sistemas de equações lineares. Esses sistemas são, de modo geral, esparsos e de grande porte, onde as incógnitas podem ser da ordem de milhares, ou até mesmo de milhões. Levando em consideração essas características, o emprego de métodos iterativos é o mais apropriado para a resolução dos sistemas gerados, devido principalmente a sua potencialidade quanto à otimização de armazenamento e eficiência computacional. Uma forma de incrementar o desempenho dos métodos iterativos é empregar uma técnica multigrid. Multigrid são uma classe de métodos que resolvem eficientemente um grande conjunto de equações algébricas através da aceleração da convergência de métodos iterativos. Considerando que a resolução de sistemas de equações de problemas realísticos pode requerer grande capacidade de processamento e de armazenamento, torna-se imprescindível o uso de ambientes computacionais de alto desempenho. Uma das abordagens encontradas na literatura técnica para a resolução de sistemas de equações em paralelo é aquela que emprega métodos de decomposição de domínio (MDDs). Os MDDs são baseados no particionamento do domínio computacional em subdomínios, de modo que a solução global do problema é obtida pela combinação apropriada das soluções obtidas em cada um dos subdomínios Assim, neste trabalho são disponibilizados diferentes métodos de resolução paralela baseado em decomposição de domínio, utilizando técnicas multigrid para a aceleração da solução de sistemas de equações lineares. Para cada método, são apresentados dois estudos de caso visando a validação das implementações. Os estudos de caso abordados são o problema da difusão de calor e o modelo de hidrodinâmica do modelo UnHIDRA. Os métodos implementados mostraram-se altamente paralelizáveis, apresentando bons ganhos de desempenho. Os métodos multigrid mostraram-se eficiente na aceleração dos métodos iterativos, já que métodos que utilizaram esta técnica apresentaram desempenho superior aos métodos que não utilizaram nenhum método de aceleração.

RST: Reuse through Speculation on Traces

In this thesis, we present a novel approach to combine both reuse and prediction of dynamic sequences of instructions called Reuse through Speculation on Traces (RST). Our technique allows the dynamic identification of instruction traces that are redundant or predictable, and the reuse (speculative or not) of these traces. RST addresses the issue, present on Dynamic Trace Memoization (DTM), of traces not being reused because some of their inputs are not ready for the reuse test. These traces were measured to be 69% of all reusable traces in previous studies. One of the main advantages of RST over just combining a value prediction technique with an unrelated reuse technique is that RST does not require extra tables to store the values to be predicted. Applying reuse and value prediction in unrelated mechanisms but at the same time may require a prohibitive amount of storage in tables. In RST, the values are already stored in the Trace Memoization Table, and there is no extra cost in reading them if compared with a non-speculative trace reuse technique. . The input context of each trace (the input values of all instructions in the trace) already stores the values for the reuse test, which may also be used for prediction. Our main contributions include: (i) a speculative trace reuse framework that can be adapted to different processor architectures; (ii) specification of the modifications in a superscalar, superpipelined processor in order to implement our mechanism; (iii) study of implementation issues related to this architecture; (iv) study of the performance limits of our technique; (v) a performance study of a realistic, constrained implementation of RST; and (vi) simulation tools that can be used in other studies which represent a superscalar, superpipelined processor in detail. In a constrained architecture with realistic confidence, our RST technique is able to achieve average speedups (harmonic means) of 1.29 over the baseline architecture without reuse and 1.09 over a non-speculative trace reuse technique (DTM).

Sistema Aldeia : programação paralela e distribuída em Java sobre Infiniband e DECK

Esse trabalho de dissertação está incluído no contexto das pesquisas realizadas no Grupo de Processamento Paralelo e Distribuído da UFRGS. Ele aborda as áreas da computação de alto desempenho, interfaces simples de programação e de sistemas de interconexão de redes velozes. A máquina paralela formada por agregados (clusters) tem se destacado por apresentar os recursos computacionais necessários às aplicações intensivas que necessitam de alto desempenho. Referente a interfaces de programação, Java tem se mostrado uma boa opção para a escrita de aplicações paralelas por oferecer os sistemas de RMI e de soquetes que realizam comunicação entre dois computadores, além de todas as facilidades da orientação a objetos. Na área a respeito de interconexão de rede velozes está emergindo como uma tentativa de padronização a nova tecnologia Infiniband. Ela proporciona uma baixa latência de comunicação e uma alta vazão de dados, além de uma série de vantagens implementadas diretamente no hardware. É neste contexto que se desenvolve o presente trabalho de dissertação de mestrado. O seu tema principal é o sistema Aldeia que reimplementa a interface bastante conhecida de soquetes Java para realizar comunicação assíncrona em agregados formados por redes de sistema. Em especial, o seu foco é redes configuradas com equipamentos Infiniband. O Aldeia objetiva assim preencher a lacuna de desempenho do sistema padrão de soquetes Java, que além de usar TCP/IP possui um caráter síncrono. Além de Infiniband, o Aldeia também procura usufruir dos avanços já realizados na biblioteca DECK, desenvolvida no GPPD da UFRGS. Com a sua adoção, é possível realizar comunicação com uma interface Java sobre redes Myrinet, SCI, além de TCP/IP. Somada a essa vantagem, a utilização do DECK também proporciona a propriedade de geração de rastros para a depuração de programas paralelos escritos com o Aldeia. Uma das grandes vantagens do Aldeia está na sua capacidade de transmitir dados assincronamente. Usando essa técnica, cálculos da aplicação podem ser realizados concorrentemente com as operações pela rede. Por fim, os canais de dados do Aldeia substituem perfeitamente aqueles utilizados para a serialização de objetos. Nesse mesmo caminho, o Aldeia pode ser integrado à sistemas que utilizem a implementação de soquetes Java, agora para operar sobre redes de alta velocidade. Palavras-chave: Arquitetura Infiniband, agregado de computadores, linguagem de programação Java, alto desempenho, interface de programação.